# -*- coding:utf-8 -*-
''''
对于字符串A，其中绝对不含有字符’.’和’*’。再给定字符串B，其中可以含有’.’或’*’，’*’字符不能是B的首字符，
并且任意两个’*’字符不相邻。exp中的’.’代表任何一个字符，B中的’*’表示’*’的前一个字符可以有0个或者多个。
请写一个函数，判断A是否能被B匹配。
给定两个字符串A和B,同时给定两个串的长度lena和lenb，请返回一个bool值代表能否匹配。保证两串的长度均小于等于300。'''
class WildMatch:
    def chkWildMatch(self, A, lena, B, lenb):
        # write code here

        if lena==0 or lenb==0:
            return False
        f = [[False] * (lenb+1) for _ in range(lena+1)]

        f[0][0] = True

        for i in range(1,lena+1):
            for j in range(1,lenb+1):
                if B[j-1] == '*':
                    # 递归那个三种情况
                    f[i][j] = f[i][j-1] or f[i-1][j] or f[i-1][j-1]
                elif B[j-1] == '.':
                    f[i][j] = f[i-1][j-1]
                else:
                    if A[i-1]==B[j-1]:
                        f[i][j] = f[i-1][j-1]

        return f[-1][-1]

s = WildMatch()
m = s.chkWildMatch("abcd",4,".*",2)
print(m)



